Fast iterative circles (and ellipses, and other figures).
Here's the entire algorithm to compute points on an elliptical arc, very quickly:
while(true)
{
x += d * y;
y -= d * x;
}
Attributed to Marvin Minsky, 1972: HAKMEM, MIT AI Memo 239 (HTML version here).
Also on a PDP-1, David Mapes
talks about finding it independently.
I've been using this to make circles since I found it by accident in the
early 1980s (using a BBC Micro). Nowadays I'm using it to make music
synthesizers (running on ARM Cortex M4).
Points per cycle
dx
dy
Initial
x
y
Loop delay (ms)
Initial conditions should put (x,y) on a unit circle somewhere, e.g. (0,1). But it works at any scale.
The delta (d) is almost exactly 6/(number of points per cycle). To be
exact: d=2.sin(pi/points). It's stable for d<2.
Small values produce more-circular circles, i.e. phases closer to 90°.
Note that the sines & cosines are perfect, it's only the phase
difference that's skewed.
If you want to fix the phase, just use (y+prev_y)/2 instead of y.
See HAKMEM items 151 & 152 for some analysis.
This page uses default Javascript numbers (IEEE double).
It's also very robust with integers, fractional integers (q7, q15, etc),
although you'll want to saturate (clip at +/-1 rather than wrap
around).
This makes it nicely applicable to microcontrollers and other small
hardware. You could use it to carve arcs, drive LEDs, make sound.
If the delta is an expression such as "0.1 * Math.pow(x,4)", you can generate some interesting nonlinear cycles.
Many nonlinear deltas will diverge rapidly. I haven't yet found good simple equations that produce continuous "chaotic" loops.
But you can go very wild with floor and modulo arithmetic.
The same principle can be applied to 3-phase: x = x-d.y+d.z; y =
y+d.x-d.z; z = z-d.x+d.y; (and presumably to higher numbers too).